﻿#region copyright
//                Copyright Andrew Rafas 2012.
// Distributed under the Eclipse Public License, Version 1.0.
//           (See accompanying file LICENSE.txt or 
//     copy at http://www.eclipse.org/legal/epl-v10.html)
#endregion
using System;

namespace CSFP
{
    public sealed class Vector<T>
    {
#if DEBUG
        public const int BitCount = 2;
#else
        public const int BitCount = 5;
#endif
        public const int BucketSize = 1 << BitCount;
        public const long IndexMask = BucketSize - 1;
        public const long OffsetMask = ~IndexMask;

        Array _root; // leafs are T[], inner  nodes (and root node if not a leaf) are Array[]
        T[] _tail; // the tail is private to this Vector, not shared with any ConstVectors
        //TODO: merge this 3 into 1 long? (6 bit shift, 53 bit tailoffset, 5 bit tailcount)
        long _tailOffset; // number of items in the tree pointed by _root (excludes items in _tail)
        int _tailCount; // number of items in _tail
        int _shift; // number of low bits to ignore in an offset to index into _root
        //long _sharedOffset; // that many number of elements are shared with one or more ConstVectors
        // _root == null && _tail == null && _tailOffset == 0 && _tailCount == 0 && _shift == 0 is a valid empty Vector

        public Vector()
        {
            _root = null;
            _tail = null;
            _tailOffset = 0;
            _tailCount = 0;
            _shift = 0;
            //_sharedOffset = 0;
        }

        public void Clear()
        {
            _root = null;
            _tail = null;
            _tailOffset = 0;
            _tailCount = 0;
            _shift = 0;
            //_sharedOffset = 0;
        }

        public long Count { get { return _tailOffset + _tailCount; } }
        public bool IsEmpty { get { return Count == 0; } }

        public void Add(T value)
        {
            //TODO: either we have not copied the tail from ConstVector, or we are empty
            if (_tailCount == BucketSize) // tail full
                AttachTailToTree(); // can change _root, _tail, _tailCount, _tailOffset, _shift
            if (_tail == null)
                _tail = new T[BucketSize];
            _tail[_tailCount] = value;
            ++_tailCount;
        }

        public T RemoveLast()
        {
            if (_tailCount > 0) {
                --_tailCount;
                T result = _tail[_tailCount];
                _tail[_tailCount] = default(T);
                return result;
            }
            DetachTailFromTree();
            return RemoveLast(); // will not recurse, _tailCount == BucketSize
        }

        public T this[long index]
        {
            get
            {
                if (index < 0)
                    throw new IndexOutOfRangeException();
                if (index >= _tailOffset) {
                    if (index >= _tailOffset + _tailCount)
                        throw new IndexOutOfRangeException();
                    return _tail[index & IndexMask];
                }
                var current = _root;
                for (int sh = _shift; sh > 0; sh -= BitCount)
                    current = ((Array[])current)[(index >> sh) & IndexMask];
                return ((T[])current)[index & IndexMask];
            }
            set
            {
                if (index < 0)
                    throw new IndexOutOfRangeException();
                if (index >= _tailOffset) {
                    if (index >= _tailOffset + _tailCount)
                        throw new IndexOutOfRangeException();
                    _tail[index & IndexMask] = value;
                    return;
                }
                var current = _root;
                for (int sh = _shift; sh > 0; sh -= BitCount)
                    current = ((Array[])current)[(index >> sh) & IndexMask];
                ((T[])current)[index & IndexMask] = value;
            }
        }

        public VectorSeq Seq { get { return new VectorSeq(this, 0, null); } }

        void AttachTailToTree()
        {
            if (_root == null) {
                _root = _tail;
                _tail = null;
                _tailOffset += _tailCount;
                _tailCount = 0;
                return;
            }
            // not a root insert, check if the tree pointed by _root is full
            if ((_tailOffset >> BitCount) == (1 << _shift)) {
                // we have to increase the height by a new _root
                Array[] newRoot = new Array[BucketSize];
                newRoot[0] = _root;
                _root = newRoot;
                _shift += BitCount;
                // and continue since in this case we have to insert intermediaries in the same way
            }
            // normal append, the height remains but there can be missing intermediary buckets
            var current = _root;
            for (int sh = _shift; true; sh -= BitCount) {
                System.Diagnostics.Debug.Assert(sh > 0, "Tried to insert into an already occupied index");
                var i = (_tailOffset >> sh) & IndexMask;
                var bucket = (Array[])current;
                var child = bucket[i];
                if (child == null) {
                    if (sh == BitCount) {
                        // we have just found its parent
                        bucket[i] = _tail;
                        _tail = null;
                        _tailOffset += _tailCount;
                        _tailCount = 0;
                        return;
                    }
                    // we have to insert an intermediary bucket
                    child = new Array[BucketSize];
                    bucket[i] = child;
                }
                current = child;
            }
        }

        void DetachTailFromTree()
        {
            if (_shift == 0) {
                _tail = (T[])_root;
                _root = null;
                _tailOffset = 0;
                _tailCount = BucketSize;
                return;
            }
            // find the parent of the prior leaf
            long index = _tailOffset - 1;
            var current = _root;
            for (int sh = _shift; sh > BitCount; sh -= BitCount)
                current = ((Array[])current)[(index >> sh) & IndexMask];
            // move the leaf to _tail
            var parent = ((Array[])current);
            var i = (index >> BitCount) & IndexMask;
            _tail = (T[])parent[i];
            parent[i] = null;
            _tailOffset -= BucketSize;
            _tailCount = BucketSize;
            // we leave unused paths in the tree, consuming at most largest_tree_size/31 more memory than necessary (3.2%)
            //TODO: decrease heigth? maybe we should trim _root when we decrease height?
            // trimming root means that if root has only 1 element, then we can get rid of it (but it can have a lot of unused intermediary nodes...)
        }

        public struct VectorSeq : ISeq<T, VectorSeq>
        {
            readonly Vector<T> _head;
            readonly long _index;
            T[] _current; // cached leaf reference

            void sync_current()
            {
                if (_index >= _head._tailOffset) {
                    _current = _head._tail;
                } else {
                    var current = _head._root;
                    for (int sh = _head._shift; sh > 0; sh -= BitCount)
                        current = ((Array[])current)[(_index >> sh) & IndexMask];
                    _current = (T[])current;
                }
            }

            public VectorSeq(Vector<T> head, long index, T[] current)
            {
                _head = head;
                _index = index;
                _current = current;
            }

            public bool IsValid { get { return _index < _head.Count; } }

            public T First
            {
                get
                {
                    if (_current == null)
                        sync_current();
                    return _current[_index & IndexMask];
                }
            }

            public VectorSeq Next
            {
                get
                {
                    var nextIndex = _index + 1;
                    return new VectorSeq(_head, nextIndex, (nextIndex & IndexMask) == 0 ? null : _current); // desync or not
                }
            }
        }
    }

    public struct ConstVector<T>
    {
        public const int BitCount = Vector<T>.BitCount;
        public const int BucketSize = Vector<T>.BucketSize;
        public const long IndexMask = Vector<T>.IndexMask;
        public const long OffsetMask = Vector<T>.OffsetMask;

    }
}
